package arbres;

import listes.Liste;
import listes.ListeDC;

public class BinarbreDC<E extends Comparable<E>> implements Binarbre<E> {
	// Un arbre Binarbre<E> est un arbre DE RECHERCHE dont les noeuds ont 0, 1 ou 2 fils.
	// Les 2 fils d'un noeud sont traditionnellement désignés par "fils gauche" et "fils droit".
	// Lorsqu'un noeud est fils unique, il a quand même une position par raport à son père (à gauche ou à droite).
	// RAPPEL : les éléments d'un arbre de recherche sont totalement ordonnables et ne
	// peuvent apparaître qu'en UNE SEULE occurrence.
	
	protected BinarbreDC<E> father;
	protected BinarbreDC<E> left;
	protected BinarbreDC<E> right;
	protected E value;
	protected int height;

	// flag lié à la classe qui indique si toString doit rajouter sur 
	// chaque noeud le facteur d'équilibrage :
	public static boolean printBalance=false;
	
	public BinarbreDC(E e) { // arbre réduit à une racine (c'est également une feuille !)
		father = null;
		left = null;
		right = null;
		value = e;
		height = 0;
	}
	
	private static String seqChar(char c, int i) {
		String res="";
		for(; i>0; i--) res+=c;
		return res;
	}
	
	private static <F extends Comparable<F>> Liste<String> niveaux(BinarbreDC<F> a) {
		String etiq = a.getVal().toString();
		if(printBalance) etiq += "("+a.balance()+")";
		if(a.isLeaf()) return new ListeDC<String>(etiq);
		Liste<String> niveauxL = (a.getLeft()==null ? new ListeDC<String>() : niveaux(a.getLeft()));
		Liste<String> niveauxR = (a.getRight()==null ? new ListeDC<String>() : niveaux(a.getRight()));
		Liste<String> res = new ListeDC<String>();
		int largeurL = (niveauxL.size()==0 ? 1 : niveauxL.get(0).length());
		int largeurR = (niveauxR.size()==0 ? -1 : niveauxR.get(0).length());
		for(int k=0; k<niveauxL.size()&& k<niveauxR.size(); k++)
			res.add(k, niveauxL.get(k)+" "+niveauxR.get(k));
		for(int k=niveauxL.size(); k<niveauxR.size(); k++)
			res.add(k, seqChar(' ', largeurL+1)+niveauxR.get(k));
		for(int k=niveauxR.size(); k<niveauxL.size(); k++)
			res.add(k, niveauxL.get(k)+seqChar(' ', largeurR+1));
		String traits=(a.getRight()==null ? "|" : "+"+seqChar('-', largeurL)+"+");
		traits += seqChar(' ', largeurL+1+largeurR-traits.length());
		res.add(0, traits).add(0, etiq+seqChar(' ', largeurL+1+largeurR-etiq.length()));
		return res;
	}
	
	public String toString() {
		Liste<String> niveaux = niveaux(this);
		String res="";
		for(int i=0; i<niveaux.size(); i++) res+=niveaux.get(i)+"\n";
		return res;
	}

	public E getVal() { // renvoie la valeur de la RACINE de l'arbre
		return value;
	}

	public boolean isLeaf() { // renvoie vrai si l'arbre est une feuille (racine sans enfants)
		return left==null && right==null;
	}

	public int familySize() { // renvoie le nombre de DESCENDANTS depuis la RACINE (racine exclue)
		return (right==null ? 0 : 1+right.familySize())+(left==null ? 0 : 1+left.familySize());
	}

	public int height() { // renvoie la hauteur de l'arbre, à partir de la RACINE
		return height;
	}
	
	public int balance() { // renvoie le facteur d'équilibrage
		return (right==null ? 0 : 1+right.height())-(left==null ? 0 : 1+left.height());
	}
	
	public BinarbreDC<E> father() { // renvoie le père de l'arbre s'il existe, ou null s'il n'existe pas
		return father;
	}

	public BinarbreDC<E> ancestor() { // renvoie le premier ancêtre de l'arbre
		// (la racine du plus grand arbre englobant) ou null s'il n'existe pas.
		if(father==null) return null;
		BinarbreDC<E> aieul = father;
		for( ; aieul.father!=null; aieul = aieul.father) {}
		return aieul;
	}

	public BinarbreDC<E> getLeft() { // renvoie le fils gauche s'il existe, ou null s'il n'existe pas
		return left;
	}

	public BinarbreDC<E> getRight() { // renvoie le fils droit s'il existe, ou null s'il n'existe pas
		return right;
	}

	public BinarbreDC<E> brother() { // renvoie le frère de l'arbre s'il existe, ou null s'il n'existe pas
		if(father==null) return null;
		if(father.left==this) return father.right;
		return father.left;
	}

	public Liste<? extends BinarbreDC<E>> ancestors() { // renvoie la liste des aieux de l'arbre
		// (dans l'ordre depuis le premier ancêtre).
		Liste<BinarbreDC<E>> res = new ListeDC<BinarbreDC<E>>();
		for(BinarbreDC<E> aieul = father; aieul!=null; aieul = aieul.father)
			res.add(0, aieul);
		return res;
	}

	public Liste<? extends BinarbreDC<E>> gen(int n) { // renvoie la liste des déscendants de la racine à la n^ème génération.
		// génération 1 : enfants ; génération 2 : petits enfants ; ...
		// quand l'indice ne correspond pas à une génération possible ou existante, la liste est vide.
		Liste<BinarbreDC<E>> res = new ListeDC<BinarbreDC<E>>();
		if(n<1) return res;
		if(n==1) {
			if(left!=null)  res.add(left);
			if(right!=null) res.add(right);
			return res;
		}
		if(left!=null)  res.addAll(left.gen(n-1));
		if(right!=null) res.addAll(right.gen(n-1));
		return res;
	}

	public boolean containsVal(E e) { // renvoie vrai si e est contenu dans l'arbre
		int comparaison=e.compareTo(this.value);
		if(comparaison==0) return true;
		if(comparaison<0 && left!=null)  return left.containsVal(e);
		if(comparaison>0 && right!=null) return right.containsVal(e);
		return false;
	}
	
	public boolean containsAll(Liste<? extends E> liste) { // renvoie vrai si tous les éléments de l apparaissent dans l'arbre
		for(int i=0; i<liste.size(); i++)
			if(!containsVal(liste.get(i))) return false;
		return true;
	}
	
	public E maxVal() { // renvoie la valeur maximum
		if (right==null) return value;
		return right.maxVal();
	}
	
	public E minVal() { // renvoie la valeur minimum
		if (left==null) return value;
		return left.minVal();
	}
	
	protected BinarbreDC<E> buildLeaf(E e) {
		// crée un arbre réduit à 1 feuille de valeur e
		// Intérêt : cette méthode peut être réécrire dans
		// les classes héritière !
		return new BinarbreDC<E>(e);
	}

	protected void updateHeight() { // met à jour la hauteur de tous les ancêtres concernés par une mise à jour
		int bakHeight = height;
		int hg = (left ==null ? -1 : left.height);
		int hd = (right==null ? -1 : right.height);
		height = (hg<hd ? hd : hg) + 1;
		if(father!=null && bakHeight!=height) father.updateHeight();
	}

	public Binarbre<E> addVal(E e) {
		// insère e dans l'arbre ; renvoie l'instance courante
		int comparaison=e.compareTo(this.value);
		if(comparaison<0)
			if(left!=null) left.addVal(e);
			else {
				left = buildLeaf(e);
				left.father = this;
				updateHeight();
			}
		if(comparaison>0)
			if(right!=null) right.addVal(e);
			else {
				right = buildLeaf(e);
				right.father = this;
				updateHeight();
			}
		return this;
	}
	
	public Binarbre<E> addAll(E... l) {
		// insère tous les éléments de l ; renvoie l'instance courante
		Binarbre<E> res = this;
		for(int i=0; i<l.length; i++) res = res.addVal(l[i]);
		return res;
	}

	public Binarbre<E> addAll(Liste<E> l) {
		// insère tous les éléments de l ; renvoie l'instance courante
		Binarbre<E> res = this;
		for(int i=0; i<l.size(); i++) res = res.addVal(l.get(i));
		return res;
	}
	
	public Binarbre<E> cutVal(E e) {
		// supprimme e dans l'arbre ;
		// renvoie l'instance courante mise à jour si la racine n'est pas supprimée ;
		// renvoie la fusion des fils si la racine est supprimée (peut être null)
		int comparaison=e.compareTo(this.value);
		if(comparaison==0) {
			if(left!=null) {
				BinarbreDC<E> maxLeft = left;
				while(maxLeft.right!=null) maxLeft = maxLeft.right;
				value = maxLeft.value;
				maxLeft.cutVal(maxLeft.value);
			}
			else if(right!=null) { 
				BinarbreDC<E> minRight = right;
				while(minRight.left!=null) minRight = minRight.left;
				value = minRight.value;
				minRight.cutVal(minRight.value);
			}
			else { // c'est une feuille
				if(father!=null) {
					if(father.left==this) father.left=null;
					else father.right=null;
					father.updateHeight();
				}
				father=null;
				return null;
			}			
		}
		if(comparaison<0 && left!=null)  left = (BinarbreDC<E>) left.cutVal(e);
		if(comparaison>0 && right!=null) right = (BinarbreDC<E>) right.cutVal(e);
		return this;
	}
	
	public Binarbre<E> cutAll(E... l) {
		// supprime tous les éléments de l ;
		// renvoie l'instance courante mise à jour si la racine n'est pas supprimée ;
		// renvoie la fusion des fils (MIS A JOUR) si la racine est supprimée (peut être null)
		Binarbre<E> candidat = this;
		for(int i=0; i<l.length; i++) candidat=candidat.cutVal(l[i]);
		return candidat;
	}

	public Binarbre<E> cutAll(Liste<E> l) {
		// idem...
		Binarbre<E> candidat = this;
		for(int i=0; i<l.size(); i++) candidat=candidat.cutVal(l.get(i));
		return candidat;
	}

	public Liste<E> prefixe() { // renvoie la liste des éléments stockés dans l'arbre		
		// dans l'ordre correspondant à son parcours préfixe
		Liste<E> res = new ListeDC<E>().add(value);
		if(left!=null) res.addAll(left.prefixe());
		if(right!=null) res.addAll(right.prefixe());
		return res;
	}

	public Liste<E> infixe() { // renvoie la liste des éléments stockés dans l'arbre
		// dans l'ordre correspondant à son parcours infixe
		Liste<E> res = new ListeDC<E>();
		if(left!=null) res.addAll(left.infixe());
		res.add(value);
		if(right!=null) res.addAll(right.infixe());
		return res;
	}

	public Liste<E> postfixe() { // renvoie la liste des éléments stockés dans l'arbre
		// dans l'ordre correspondant à son parcours postfixe
		Liste<E> res = new ListeDC<E>();
		if(left!=null) res.addAll(left.postfixe());
		if(right!=null) res.addAll(right.postfixe());
		return res.add(value);
	}

	public Liste<E> largeur() { // renvoie la liste des éléments stockés dans l'arbre
		// niveau par niveau à partir de la racine
		Liste<E> res = new ListeDC<E>().add(value);
		int height = height();
		for (int n = 1; n <= height; n++) {
			Liste<? extends BinarbreDC<E>> niveaux = gen(n);
			for (int i = 0; i < niveaux.size(); i++) res.add(niveaux.get(i).value);
		}
		return res;
	}
	
	private BinarbreDC<E> creeArbre(Liste<E> l) {
		if(l.size()==1) return buildLeaf(l.get(0));
		if(l.size()==2) return (BinarbreDC<E>) buildLeaf(l.get(0)).addVal(l.get(1));
		int milieu = l.size()/2;
		BinarbreDC<E> res = buildLeaf(l.get(milieu));
		res.left = creeArbre(l.subList(0, milieu-1));
		res.right = creeArbre(l.subList(milieu+1, l.size()-1));
		res.left.father = res;
		res.right.father = res;
		// On met à jour la hauteur :
		res.updateHeight();
		return res;
	}
	
	public Binarbre<E> equilibre() { // équilibre l'arbre ; renvoie l'instance courante
		BinarbreDC<E> a = creeArbre(infixe());
		if(left!=null)  left.father=null;
		if(right!=null) right.father=null;
		value = a.value;
		left = a.left;
		right = a.right;
		height = a.height;
		if(left!=null)  left.father=this;
		if(right!=null) right.father=this;
		return this;
	}

	public static void main(String[] args) {
		Binarbre<Integer> a1 = new BinarbreDC<Integer>(1).addAll(2,3,4,5);
		Binarbre<Integer> a2 = new BinarbreDC<Integer>(5).addAll(4,3,2,1);
		Binarbre<Integer> a3 = new BinarbreDC<Integer>(10).addAll(5, 12, 11, 8, 9, 4, 2, 10, 5, 11, 10); 
		System.out.println(a1+"*** a1 : "+a1.familySize()+" descendants ; hauteur : "+a1.height()+" contient 3 et 9 ? "+a1.containsVal(3)+a1.containsVal(9));
		System.out.println(a2+"*** a2 : "+a2.familySize()+" descendants ; hauteur : "+a2.height()+" contient 3 et 9 ? "+a2.containsVal(3)+a2.containsVal(9));
		System.out.println(a3+"*** a3 : "+a3.familySize()+" descendants ; hauteur : "+a3.height()+" contient 3 et 9 ? "+a3.containsVal(3)+a3.containsVal(9));
		System.out.println("*** generation 0 dans a3 :\n"+a3.gen(0));
		System.out.println("*** generation 1 dans a3 :\n"+a3.gen(1));
		System.out.println("*** generation 2 dans a3 :\n"+a3.gen(2));
		System.out.println("*** generation 3 dans a3 :\n"+a3.gen(3));
		System.out.println("*** generation 4 dans a3 :\n"+a3.gen(4));
		System.out.println("*** generation 5 dans a3 :\n"+a3.gen(5));
		System.out.println("*** generation 6 dans a3 :\n"+a3.gen(6));
		System.out.println(a1+"*** a1 : "+a1.prefixe());
		System.out.println("*** a1 : "+a1.infixe());
		System.out.println("*** a1 : "+a1.postfixe());
		System.out.println("*** a1 : "+a1.largeur());
		System.out.println(a2+"*** a2 : "+a2.prefixe());
		System.out.println("*** a2 : "+a2.infixe());
		System.out.println("*** a2 : "+a2.postfixe());
		System.out.println("*** a2 : "+a2.largeur());
		System.out.println(a3+"*** a3 : "+a3.prefixe());
		System.out.println("*** a3 : "+a3.infixe());
		System.out.println("*** a3 : "+a3.postfixe());
		System.out.println("*** a3 : "+a3.largeur());
		System.out.println("############# ON IMPRIME EN PLUS L'EQUILIBRAGE");
		BinarbreDC.printBalance=true;
		System.out.println("EQUILIBRAGE arbre 1 noeud :\n"+new BinarbreDC<Integer>(1).equilibre());
		System.out.println("EQUILIBRAGE arbre 2 noeud :\n"+new BinarbreDC<Integer>(1).addVal(2).equilibre());
		System.out.println("EQUILIBRAGE de :\n"+a1+"=>\n"+a1.equilibre()+"(hauteur : "+a1.height()+")");
		System.out.println("EQUILIBRAGE de :\n"+a2+"=>\n"+a2.equilibre()+"(hauteur : "+a2.height()+")");
		System.out.println("EQUILIBRAGE de :\n"+a3.addAll(13,14,15,16,17,18,19)+"=>\n"+a3.equilibre()+"(hauteur : "+a3.height()+")");
		System.out.println("#############");
		System.out.println("a3 :\n"+a3+"** - 3 :"); a3 = a3.cutVal(3); System.out.println(a3+"(hauteur : "+a3.height()+")"); 
		System.out.println("** - 9 :"); a3 = a3.cutVal(9); System.out.println(a3+"(hauteur : "+a3.height()+")"); 
		System.out.println("** - 14 :"); a3 = a3.cutVal(14); System.out.println(a3+"(hauteur : "+a3.height()+")"); 
		System.out.println("** - 16 :"); a3 = a3.cutVal(16); System.out.println(a3+"(hauteur : "+a3.height()+")"); 
		System.out.println("** - 12 :"); a3 = a3.cutVal(12); System.out.println(a3+"(hauteur : "+a3.height()+")"); 
		System.out.println("EQUILIBRAGE :\n"+a3.equilibre()+"(hauteur : "+a3.height()+")");
		/*
			1        
			+-+      
			  2      
			  +-+    
			    3    
			    +-+  
			      4  
			      +-+
			        5
			*** a1 : 4 descendants ; hauteur : 4 contient 3 et 9 ? truefalse
			5
			|
			4
			|
			3
			|
			2
			|
			1
			*** a2 : 4 descendants ; hauteur : 4 contient 3 et 9 ? truefalse
			10      
			+-----+ 
			5     12
			+-+   | 
			4 8   11
			| +-+   
			2   9   
			*** a3 : 7 descendants ; hauteur : 3 contient 3 et 9 ? truefalse
			*** generation 0 dans a3 :
			( )
			*** generation 1 dans a3 :
			( 5    
			+-+  
			4 8  
			| +-+
			2   9
			 12
			| 
			11
			 )
			*** generation 2 dans a3 :
			( 4
			|
			2
			 8  
			+-+
			  9
			 11
			 )
			*** generation 3 dans a3 :
			( 2
			 9
			 )
			*** generation 4 dans a3 :
			( )
			*** generation 5 dans a3 :
			( )
			*** generation 6 dans a3 :
			( )
			1        
			+-+      
			  2      
			  +-+    
			    3    
			    +-+  
			      4  
			      +-+
			        5
			*** a1 : ( 1 2 3 4 5 )
			*** a1 : ( 1 2 3 4 5 )
			*** a1 : ( 5 4 3 2 1 )
			*** a1 : ( 1 2 3 4 5 )
			5
			|
			4
			|
			3
			|
			2
			|
			1
			*** a2 : ( 5 4 3 2 1 )
			*** a2 : ( 1 2 3 4 5 )
			*** a2 : ( 1 2 3 4 5 )
			*** a2 : ( 5 4 3 2 1 )
			10      
			+-----+ 
			5     12
			+-+   | 
			4 8   11
			| +-+   
			2   9   
			*** a3 : ( 10 5 4 2 8 9 12 11 )
			*** a3 : ( 2 4 5 8 9 10 11 12 )
			*** a3 : ( 2 4 9 8 5 11 12 10 )
			*** a3 : ( 10 5 12 4 8 11 2 9 )
			############# ON IMPRIME EN PLUS L'EQUILIBRAGE
			EQUILIBRAGE arbre 1 noeud :
			1(0)
			
			EQUILIBRAGE arbre 2 noeud :
			1(1)  
			+-+   
			  2(0)
			
			EQUILIBRAGE de :
			1(4)        
			+-+         
			  2(3)      
			  +-+       
			    3(2)    
			    +-+     
			      4(1)  
			      +-+   
			        5(0)
			=>
			3(0)         
			+------+     
			1(1)   4(1)  
			+-+    +-+   
			  2(0)   5(0)
			(hauteur : 2)
			EQUILIBRAGE de :
			5(-4)
			|    
			4(-3)
			|    
			3(-2)
			|    
			2(-1)
			|   
			1(0)
			=>
			3(0)         
			+------+     
			1(1)   4(1)  
			+-+    +-+   
			  2(0)   5(0)
			(hauteur : 2)
			EQUILIBRAGE de :
			10(5)                               
			+------------+                      
			5(0)         12(6)                  
			+-----+      +-----+                
			4(-1) 8(1)   11(0) 13(6)            
			|    +-+          +-+              
			2(0)   9(0)         14(5)          
			                     +-+            
			                       15(4)        
			                       +-+          
			                         16(3)      
			                         +-+        
			                           17(2)    
			                           +-+      
			                             18(1)  
			                             +-+    
			                               19(0)
			=>
			12(0)                                       
			+--------------------+                      
			8(0)                 16(0)                  
			+---------+          +-----------+          
			4(0)      10(0)      14(0)       18(0)      
			+----+    +----+     +-----+     +-----+    
			2(0) 5(0) 9(0) 11(0) 13(0) 15(0) 17(0) 19(0)
			(hauteur : 3)
			#############
			a3 :
			12(0)                                       
			+--------------------+                      
			8(0)                 16(0)                  
			+---------+          +-----------+          
			4(0)      10(0)      14(0)       18(0)      
			+----+    +----+     +-----+     +-----+    
			2(0) 5(0) 9(0) 11(0) 13(0) 15(0) 17(0) 19(0)
			** - 3 :
			12(0)                                       
			+--------------------+                      
			8(0)                 16(0)                  
			+---------+          +-----------+          
			4(0)      10(0)      14(0)       18(0)      
			+----+    +----+     +-----+     +-----+    
			2(0) 5(0) 9(0) 11(0) 13(0) 15(0) 17(0) 19(0)
			(hauteur : 3)
			** - 9 :
			12(0)                                    
			+-----------------+                      
			8(0)              16(0)                  
			+---------+       +-----------+          
			4(0)      10(1)   14(0)       18(0)      
			+----+    +-+     +-----+     +-----+    
			2(0) 5(0)   11(0) 13(0) 15(0) 17(0) 19(0)
			(hauteur : 3)
			** - 14 :
			12(0)                                
			+-----------------+                  
			8(0)              16(0)              
			+---------+       +-------+          
			4(0)      10(1)   13(1)   18(0)      
			+----+    +-+     +-+     +-----+    
			2(0) 5(0)   11(0)   15(0) 17(0) 19(0)
			(hauteur : 3)
			** - 16 :
			12(0)                              
			+-----------------+                
			8(0)              15(1)            
			+---------+       +-----+          
			4(0)      10(1)   13(0) 18(0)      
			+----+    +-+           +-----+    
			2(0) 5(0)   11(0)       17(0) 19(0)
			(hauteur : 3)
			** - 12 :
			11(0)                            
			+---------------+                
			8(-1)           15(1)            
			+---------+     +-----+          
			4(0)      10(0) 13(0) 18(0)      
			+----+                +-----+    
			2(0) 5(0)             17(0) 19(0)
			(hauteur : 3)
			EQUILIBRAGE :
			11(0)                         
			+--------------+              
			5(0)           17(0)          
			+------+       +-------+      
			2(1)   8(1)    13(1)   18(1)  
			+-+    +-+     +-+     +-+    
			  4(0)   10(0)   15(0)   19(0)
			(hauteur : 3)
		 */
	}

}
